#include <gtest/gtest.h>

#include <vector>

#include "algorithm/backtrack/include/aroundArea.h"
#include "algorithm/backtrack/include/combinationSum.h"
#include "algorithm/backtrack/include/letterCombinations.h"
#include "algorithm/backtrack/include/movingCount.h"
#include "algorithm/backtrack/include/numIslands.h"
#include "algorithm/backtrack/include/permuteUnique.h"
#include "algorithm/backtrack/include/printNumbers.h"
#include "algorithm/backtrack/include/subsets.h"
#include "algorithm/common/include/utils.h"

TEST(TestMovingCount, BacktrackSuits) {
    EXPECT_EQ(movingCountDfs(2, 3, 1), 3);
    EXPECT_EQ(movingCountDfs(7, 2, 3), 7);
    EXPECT_EQ(movingCountDfs(4, 6, 15), 24);
    EXPECT_EQ(movingCountDfs(4, 6, 7), 23);

    EXPECT_EQ(movingCount(2, 3, 1), 3);
    EXPECT_EQ(movingCount(7, 2, 3), 7);
    EXPECT_EQ(movingCount(4, 6, 15), 24);
    EXPECT_EQ(movingCount(4, 6, 7), 23);
}

TEST(TestNumIsLands, SearchSuits) {
    vector<vector<char>> grids = {{'1', '1', '1', '1', '0'},
                                  {'1', '1', '0', '1', '0'},
                                  {'1', '1', '0', '0', '0'},
                                  {'0', '0', '0', '0', '0'}};

    EXPECT_EQ(numIslands(grids), 1);
    grids = {{'1', '1', '0', '0', '0'},
             {'1', '1', '0', '0', '0'},
             {'0', '0', '1', '0', '0'},
             {'0', '0', '0', '1', '1'}};
    EXPECT_EQ(numIslands(grids), 3);
    grids = {{'1', '1', '1', '1', '0'},
             {'1', '1', '0', '1', '0'},
             {'1', '1', '0', '0', '0'},
             {'0', '0', '0', '0', '0'}};
    EXPECT_EQ(numIslands(grids), 1);
}

TEST(TestAroundArea, BaseGraphTest) {
    std::vector<std::vector<char>> board = {{'X', 'X', 'X', 'X'},
                                            {'X', 'O', 'O', 'X'},
                                            {'X', 'X', 'O', 'X'},
                                            {'X', 'O', 'X', 'X'}};
    aroundArea(board);
    std::vector<std::vector<char>> truth = {{'X', 'X', 'X', 'X'},
                                            {'X', 'X', 'X', 'X'},
                                            {'X', 'X', 'X', 'X'},
                                            {'X', 'O', 'X', 'X'}};
    board = {{'O', 'O'}, {'O', 'O'}};
    aroundArea(board);
    truth = {{'O', 'O'}, {'O', 'O'}};
    EXPECT_TRUE(valuesIsSame(board, truth));
}

TEST(TestPermuteUnique, BaseGraphTest) {
    vector<int> nums = {1, 1, 2};
    vector<vector<int>> truth = {{1, 1, 2}, {1, 2, 1}, {2, 1, 1}};
    auto result = permuteUnique(nums);
    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < truth[i].size(); j++) {

            EXPECT_EQ(result[i][j], truth[i][j]);
        }
    }
}

TEST(TestCombinationSum, BaseGraphTest) {
    vector<int> nums = {2, 3, 6, 7};
    auto result = combinationSum(nums, 7);
    vector<vector<int>> truth = {{2, 2, 3}, {7}};

    EXPECT_EQ(result.size(), truth.size());
}

TEST(TestPrintNumbers, BaseGraphTest) {
    std::vector<string> res = printNumbers(1);
    vector<string> truth = {"1", "2", "3", "4", "5", "6", "7", "8", "9"};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth, res);
    }
    res = printNumbers(2);
    truth = {};
    for (int i = 1; i < 100; i++)
        truth.emplace_back(std::to_string(i));

    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth, res);
    }
}

TEST(TestLetterCombinations, CommonSuits) {
    auto nums = letterCombinations("23");
    vector<string> truth = {"ad", "ae", "af", "bd", "be",
                            "bf", "cd", "ce", "cf"};
    for (int i = 0; i < nums.size(); i++) {
        EXPECT_EQ(nums[i], truth[i]);
    }
}

TEST(TestCombinationSum2, CommonSuits) {
    vector<int> candidates = {10, 1, 2, 7, 6, 1, 5};
    auto result = combinationSum2(candidates, 8);
    vector<vector<int>> truth = {{1, 1, 6}, {1, 2, 5}, {1, 7}, {2, 6}};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_TRUE(valuesIsSame(truth[i], result[i]));
    }
}

TEST(TestSubSets, CommonSuits) {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> truth = {{},  {1},    {2},    {1, 2},
                                 {3}, {1, 3}, {2, 3}, {1, 2, 3}};
    auto res = subsets(nums);
    EXPECT_EQ(truth.size(), res.size());
}
